package class6;

import common.ArrayUtils;

/**
 * https://leetcode.cn/problems/sort-colors/description/
 * 颜色分类
 * 荷兰国旗问题
 * 一串数组，分为[5< =5 >5]
 * <p>
 * [3, 5, 6, 3, 4, 5, 2, 6, 9, 0]
 * low                         high
 * i
 */
public class Code06_sortColor {

    static int[] model = {3, 5, 6, 3, 4, 5, 2, 6, 9, 0};

    public static void main(String[] args) {
        int[] arr = {3, 5, 6, 3, 4, 5, 2, 6, 9, 0};
        int num = 5;
        sortColor(arr, num);
        ArrayUtils.printArr(arr);

    }

    private static void sortColor(int[] arr, int num) {
        int less = 0, more = arr.length - 1, index = 0;

        while (index <= more) {
            // 如果当前元素小于 num，则将当前元素与 less 指向的位置互换，并将 index 和 less 向前移动一步
            if (arr[index] < num) { // 小于num
                swap(arr, index++, less++);
            } else if (arr[index] > num) { // 大于num
                // 如果当前元素大于 num，则将当前元素与 more 指向的位置互换，但此时 index 不需要移动，因为要检查交换过来的新元素是什么
                swap(arr, index, more--);
            } else {
                // 如果当前元素等于 num，则直接将 index 向前移动一步
                index++;
            }
        }
    }


    public static void swap(int[] arr, int x, int y) {
        int t = arr[x];
        arr[x] = arr[y];
        arr[y] = t;
    }
}
